package recursion;

import java.util.ArrayList;

public class D230811 {
    // 括号生成
    // 求 n 对括号的合法组成
    // 用 left 和 right 记录当前左右括号的数量
    // 进行递归
    ArrayList<String> ret = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        func(new StringBuilder(), n, 0, 0);
        return ret;
    }
    public void func(StringBuilder sb, int n, int left, int right) {
        if (sb.length() == 2 * n) {
            // 长度到达 2 * n, 结束递归
            ret.add(sb.toString());
            return;
        }
        if (left < n) {
            // left 只要 小于 n, 就可以添加左括号
            sb.append('(');
            func(sb, n, left + 1, right);
            // 回溯, 递归回来后去掉, 然后才能去递归另一个分支
            sb.deleteCharAt(sb.lastIndexOf("("));
        }
        if (right < left) {
            // 右括号只有小于左括号才能添加
            sb.append(')');
            func(sb, n, left, right + 1);
            sb.deleteCharAt(sb.lastIndexOf(")"));
        }
    }


    // 矩阵最长递增路径
    int maxCount = 0;
    boolean[][] flg;
    int[][] direct = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int solve (int[][] matrix) {
        // write code here
        flg = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                func(matrix, i, j, 1);
            }
        }
        return maxCount;
    }
    private void func (int[][] matrix, int x, int y, int count) {
        flg[x][y] = true;
        maxCount = Math.max(maxCount, count);
        for (int i = 0; i < 4; i++) {
            int row = x + direct[i][0];
            int col = y + direct[i][1];
            if (row >= 0 && row < matrix.length && col >= 0 && col < matrix[0].length
                    && !flg[row][col] && matrix[row][col] > matrix[x][y]) {
                func(matrix, row, col, count + 1);
            }
        }
        // 回溯
        flg[x][y] = false;
    }


    // N 皇后问题
    private int res = 0;
    public int Nqueen (int n) {
        // 使用一个一维数组来表示皇后的位置，下标为行号，元素值为列号
        // 每个子问题，与记录数组对比，检查是否符合条件
        int[] pos = new int[n];
        recursion(n, 0, pos);
        return res;
    }
    private void recursion(int n, int row, int[] pos) {
        if (row == n) {
            // 到达最后一行
            res++;
            return;
        }
        for (int i = 0; i < n; i++) {
            // 选择当前行的所有合法位置进行递归
            if (isValid(pos, row, i)) {
                pos[row] = i;
                // 递归下一行
                recursion(n, row + 1, pos);
            }
        }
    }
    // 检查当前位置是否合法
    private boolean isValid(int[] pos, int row, int col) {
        // pos 数组，下标代表行号，元素值代表列好
        for (int i = 0; i < row; i++) {
            // 不能 同行、同列、同一斜线
            if (row == i || col == pos[i]
                    || Math.abs(row - i) == Math.abs(col - pos[i])) {
                return false;
            }
        }
        return true;
    }
}
